This invention relates to a system for efficiently providing reserved rates to multiple flows at a network interface. Broadly speaking, the invention involves the determination of what packets to deliver immediately and what packets to queue or drop. More specifically, the present invention is concerned with quality of service guarantees or contracts for network bandwidth to various subscribers or customers. This level of service is treated as a contract, which should not be broken at the service provider level. The relevant component in the present invention is an interface such as a router interface, which makes differing levels of service available for various traffic flows.
Having enough bandwidth has increasingly become a problem particularly on wide area networks such as the Internet. Multiple users often must transmit information over the same limited capacity physical lines. Service providers often specify levels of service in terms of xe2x80x9creserved ratesxe2x80x9d and xe2x80x9cpeak rates.xe2x80x9d
These rates guarantee that for the multiple users accessing a specific network device, all of the users will be assured at least their reserved rate. Furthermore, data flows must be allowed to have actual transmission rates between the specified reserved and peak rates. The sum of the reserved rates often is equivalent to an interface""s entire bandwidth.
Because some data flows are allowed to burst up to a peak rate, it is possible that in the very short term, not all data flows will be able to transmit data at their reserved rates at a specified moment in time. Dropping or queueing the packets according to a xe2x80x9ctraffic-shaping algorithmxe2x80x9d is often the only alternative, but any system for dropping or queueing must still guarantee that the perceived rate as seen by the user never falls below the reserved rate.
Current methods to solve the problem include schemes such as Weighted Fair Queuing and its variant Self Clocked Fair Queueing. These systems provide a way to handle delay-sensitive traffic in an expeditious way while fairly sharing the remaining bandwidth between other data flows. These systems sort packets in a queue based on the start time offset by the product of the length of packet and a weight that represents the packet data flow""s share of the bandwidth. These schemes are well known in the art.
Unfortunately, such schemes require sorting the packets for placement in a queue. These sorting schemes do not scale well as the number of data flows increases for a particular interface. Specifically, these schemes typically have processing overhead that grows linearly, and at best, logarithmically as a fraction of the number of flows.
What is needed is an improved scheme for transmitting, queuing, or dropping packets at a network interface that minimizes overhead while guaranteeing reserved rates and fairly allocating the remaining bandwidth to the various flows on the network interface.
The present invention provides a flow control system that effectively provides reserved rates for multiple connections at the interface of a network device.
Quality of service is critical to maintaining efficient delivery of data under a variety of requirements and constraints. Voice data must be transmitted at a constant bit rate, video at a psuedo-constant bit rate, and data at an efficient best efforts rate. Multiple transmissions often must proceed simultaneously on a single medium. The present invention provides management of multiple flows at a network device interface such as a router interface to assure maximum usage of the bandwidth available on the physical line while guaranteeing minimum reserved rates for individual flows. This invention is particularly applicable to cable and fiber optic infrastructure, but is pertinent to any lines capable of handling multiple flows simultaneously over that same line.
One aspect of the invention relates to a system for controlling data transmission rates for various flows connected to a network device interface. The system can be characterized as follows: (1) one or more processors; (2) memory coupled to at least one of said one or more processors; (3) a reserved rate meter for each flow, where each meter is configured to track the use of reserved bandwidth associated with the flow; (4) a peak rate meter for each flow, where each meter is configured to track the use of maximum bandwidth associated with the flow; and (5) an interface meter configured to track the use of bandwidth of said network device interface, wherein at least one processor is configured or designed to adjust the meters based on the amount of data transmitted and refresh the meters based on the network device bandwidth.
The present invention has a number of convenient embodiments. A meter can be incremented or decremented based on bandwidth usage. The network device interface can have an interface meter associated with it to track the amount of physical bandwidth available. When the interface meter hits zero, the system can recognize that no network device bandwidth is available for transmission of additional packets. The interface meter can be refreshed at distinct intervals, and the interface meter can be incremented to reflect this update. Although a meter level of zero can conveniently indicate the unavailability of bandwidth, other meter levels can be used as well.
These meters indicate bandwidth availability in relation to the flow""s reserved and peak rates as well as in relation to the network device interface. These meters track the usage of bandwidth across the network device interface as well as across the individual flows. The peak and reserved meters are refreshed based on the associated peak and reserved rates and the interface meter is refreshed based on the network device bandwidth. If a particular flow has depleted its reserved bandwidth and either its peak bandwidth or interface bandwidth based on data transmissions, the system can determine how long a particular piece of data should be buffered (a xe2x80x9ctraffic-shaping delayxe2x80x9d) until it can be put on the network. In one embodiment of the invention, the system can, via a traffic-shaping algorithm, select a queue based upon the length of time so that the chosen queue has a dequeuing time that matches the traffic-shaping delay.
Meters provide a convenient way of practicing one embodiment of the invention, but many other embodiments exist. Token buckets may conveniently serve as one form of meter. Empty buckets indicate that the interface bandwidth, reserved bandwidth, or the peak bandwidth have been consumed. Buckets containing tokens indicate the amount of bandwidth available for use by a particular flow.
One aspect of the invention relates to a method of controlling data queuing at an interface such as a router interface. The method may be characterized by the following sequence: (1) providing a token bucket representation of the bandwidth available at the network device interface; (2) providing token buckets for each flow representing the reserved rate and peak rate associated with each particular flow; (3) refreshing the number of tokens in each bucket based on the data transmitted and bandwidth usage of each flow; and (4) subtracting the number of tokens equivalent to the size of a packet from the interface, peak, and reserved token buckets associated with a packet enqueued to output when the associated reserved token bucket is not empty or both the interface and associated peak token buckets are not empty. During this subtraction process, the peak and reserved token bucket values can sometimes turn negative.
These token buckets track the usage of bandwidth across the network device interface and across the various flows connected to the interface. Tokens are added at rates equivalent to the reserved and peak rates for the individual flows and at a rate equivalent to the network device bandwidth for the interface token bucket.
Another aspect of the invention provides an apparatus for controlling data flow through a network. The apparatus may be characterized by the following features: (1) one or more processors; (2) memory coupled to at least one of the one or more processors; (3) a plurality of token buckets associated with the reserved and peak rates for each data flow; (4) a token bucket associated with the bandwidth for the network device interface; (5) the system wherein the processor is configured or designed to send the data from a flow to output if either the reserved token value is not zero or the interface token value and the peak token value are not zero.
The processors are configured or designed to allow data transmission for a particular flow when that flow has enough tokens in the required buckets. The processors are designed to refresh token buckets at certain intervals. These refresh and updates can occur either by interrupt or by event. Interrupt driven refresh would allow more systematic updates to the token buckets, but would require greater overhead at the network device level. Event driven updates would refresh and update token buckets only upon the receipt of data of the triggering of an event. Both are effective for the present invention. The processors are also designed to account for overuse of bandwidth by debiting the token buckets appropriately for a flow that has used more than its allocated bandwidth. This debit can then be used by the processor to adjust the queuing delay for future data packets on the particular data flow. The one or more processors may have additional roles. For example, they may determine the network traffic-shaping delay required for the data. And, based upon the delay, the one or more processors may discard data or enqueue data according to a traffic-shaping algorithm.
As suggested above, the flow control system is designed for use with a large number of bursty flows. Some flows may always be transmitting at rates between their reserved and peak rates. Others may never reach their peak rate while still other flows may consistently seek to transmit at rates above their assigned peak rates. The processor or apparatus generally must guarantee that all flows get at least their reserved rates while maximizing usage of available bandwidth. The data that can not be transmitted at a particular time must be queued or dropped in a fair manner based on the prior bandwidth usage of that particular flow. Data that is queued must be traffic shaped based on a delay that is associated bandwidth over-usage.
Embodiments of the present invention further relate to a computer-readable medium including instructions for applying the above mentioned interfaces and methods. These and other features of the present invention will be described in more detail below in the detailed description of the invention and in conjunction with the following figures.
These and other features and advantages of the present invention will be described below with reference to the associated drawings.